A wireless multi-hop network is usually a wireless network without the support of base stations, such as a mobile ad-hoc network (MANET), sensor network, or wireless mesh network (WMN). Without base stations, wireless networks provide high flexibility but are limited to using existing communication methods designed for infrastructure directly. Accordingly, the address allocation in a wireless multi-hop network may be more complicated to maintain efficiency and uniqueness.
Traditionally, a host can configure its address statically or dynamically. In the static configuration, users may need to acquire an available address in advance and manually configure the address. However, it may not be reasonable for users to do manual configuration in a flexible multi-hop network. Another choice is dynamic configuration, which allows a host to configure an address dynamically, such as by use of a Dynamic Host Configuration Protocol (DHCP).
DHCP is a centralized allocation mechanism, which deploys at least one fixed server to manage all addresses in the network. FIG. 1 shows typical components in a DHCP system and messages they exchange. As shown, there are two DHCP servers 11, 12 and one DHCP relay 13 for DHCP server 12. When a new host 14 joins a multi-hop wireless network, it broadcasts a DHCP_Discover message to request an address. All hosts in the network except DHCP relay 13 will help rebroadcast this message until it reaches DHCP servers 11, 12. The DHCP relay 13 will unicast the message to the DHCP server 12 directly. Upon receiving the DHCP_Discover message, each of the DHCP servers 11, 12 will allocate an address and send a DHCP_Offer message with the address back to the new host 14. Therefore, the new host 14 may receive multiple DHCP_Offer messages to choose between. New host 14 then broadcasts a DHCP_Request message to inform all servers 11, 12 of its choice, for example server 12. The chosen server 12 will check if the allocated address is really available and, if available, sends a DHCP_Ack to the new host 14. At this time, the new host 14 can configure the allocated address as its address and start the process of DAD (Duplicate Address Detection) to guarantee that no other hosts in the network use such an address. After a lease time, which is assigned by the server 12 notifying how long the host 14 can use the allocated address, the host 14 reclaims the address by DHCP_Request. If the address is still available, the server 12 will send a DHCP_Ack message to the host 14. Otherwise, a DHCP_Nack message will be sent and the host 14 needs to perform the whole procedure starting from broadcasting DHCP_Discover again.
In view of the message flows of DHCP, it is known that, in dynamic configurations, broadcasts are usually necessary to acquire an address or detect an address conflict. However, using a broadcast in a wireless multi-hop network is very expensive and may cause a broadcast storm problem.
In the known address allocation mechanisms, self-configuration is a distributed address allocation mechanism, in which a host can configure its address by itself according to different factors, such as its hardware address (S. Cheshire, B. Aboba, and E. Guttman, Dynamic Configuration of IPv4 Link-Local Addresses, draft-ietf.zeroconf-ipv4-linklocal-17.txt, IETF Zeroconf Working Group, July 2004; S. Thomson and T. Narten, IPv6 Stateless Address Autoconfiguration, RFC 2462, December 1998) or a random number (C. E. Perkins, J. T. Malinen, R. Wakikawa, E. M. Belding-Royer, and Y. Sun, IP Address Autoconfiguration for Ad Hoc Networks, draft-ietfmanet-autoconf-01.txt, IETF MANET Working Group, July 2000). Since a self-configured address is generated by an individual host, the address has to be checked by DAD to confirm that it is not occupied by other hosts. Therefore, broadcasts are still necessary to detect address confliction.
MANETconf (S, Nesargi, and R. Prakash, MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network, INFOCOM 2002) is also a distributed method of address allocation in MANET by making all hosts record used addresses, wherein a new host acquires an address from one of its neighbors, and the neighbor finds an address not existing in its record and asks for confirmation by all other hosts in the MANET. If the address is not used by any other host, it will be assigned to the new host. In MANETconf, since confirmations are required from all other hosts, broadcasts are still required.
Prophet address allocation (H. Zhou, L. M. Ni, and M. W. Mutka, Prophet address allocation for large scale MANETs, INFOCOM 2003) tries to find a function which can generate a unique sequence of addresses for each host to be assigned in order. As a result, each host can directly assign addresses in the order of its address sequence without asking other hosts. However, it can be complex to maintain uniqueness between sequences, and the uniqueness is difficult to achieve when the address space is small. As a result, prophet address allocation is limited in a MANET with a large address space.
In US Publication No. US2004/0174904A1 for a “Method of allocating IP address and detecting duplication of IP address in an ad-hoc network environment”, each host maintains a history table and a DAD table. The history table of a host stores the address history information of the host. The DAD table stores all neighbor address information. A ‘HELLO’ message is sent periodically between neighbors to update DAD tables. When a host needs an address, it sends a request message to its neighbors. If a neighbor finds such address in its DAD table, it will send a response message with an available message to the host, whereas other neighbors finding no such addresses in their DAD tables keep silent. If the host receives a response message from its neighbors, it sends a request message with such address for duplicate detection again. The process of duplicate detection will continue until no response message is received for N times. Such a method does not involve a broadcast in the whole network. However, ‘HELLO’ messages between neighbors are always sent periodically. This can still cause significant signal overhead in the network.
Furthermore, traditional wireless multi-hop networks use routing protocols that are modified versions of routing protocols used in ad hoc networks. These protocols can be classified as reactive, proactive, and hybrid protocols. Reactive protocols, such as AODV (Ad hoc On-demand Distance Vector), allow for a sending host to broadcast a route request to all of its neighbors, each neighbor in turn rebroadcasting the route request to its neighbors, and so on, until the destination host is found. Hosts using proactive protocols, such as OLSR (Optimized Link State Routing), periodically exchange their link status with each other to maintain routing paths to the other hosts. Finally, hybrid protocols, such as ZRP (Zone Routing Protocol), combine the reactive and proactive protocols by maintaining routing information using a periodic exchange of link status only within particular zones. Hosts using the ZRP then use the reactive protocol to access hosts that are located in different zones. Therefore, all of these ad hoc protocols require an extensive exchange of information with other hosts in order to configure a routing path. This can be undesirable because it may lead to added overhead and increased latency in the network.